package Algorithm.DynamicPlanning;

import java.util.TreeSet;

public class Code21_subMatrixSumCloseToK {

    public static int subMatrixSum(int[][] ma, int K){
        if (ma == null || ma.length == 0 || ma[0].length == 0){
            return -1;
        }
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < ma.length; i++) {
            int[] arr = new int[ma[0].length];
            for (int j = i; j < ma.length; j++) {
                for (int k = 0; k < ma[0].length; k++) {
                    arr[k] += ma[j][k];
                }
                res = Math.max(res, arraySum(arr, K));
            }
        }
        return res;
    }

    public static int arraySum(int[] arr, int k){
        int sum = 0;
        int max = Integer.MIN_VALUE;
        TreeSet<Integer> set = new TreeSet<>();
        set.add(0);
        for (int i = 0; i < arr.length; i++) {
            if (set.ceiling(sum - k) != null) {
                max = Math.max(max, sum - set.ceiling(sum - k));
            }
            sum += arr[i];
            set.add(sum);
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] ma = new int[1][5];
        for (int i = 0; i < ma.length; i++) {
            for (int j = 0; j < ma[0].length; j++) {
                ma[i][j] = j + 1;
            }
        }
        System.out.println(subMatrixSum(ma, 8));
    }
}
